Autor obrázku: Chris Martin http://en.wikipedia.org/wiki/User:Booyabazooka

Kombinatorické myšlení

Kombinatorika trochu jinak

Kombinace II

diskuze, ke stažení v PDF: zadání

Úloha č. 1

Hokejový zápas NHL mezi týmy Tampa Bay Lightning () a Florida Panthers () dopadl 3:4 pro Floridu. Mezi střelce zápasu se zapsali: Jaromír Jágr , Aleksander Barkov , Brad Boyes , Aaron Ekblad , Anton Stralman , Steven Stamkos a Tyler Johnson .

(a) Kolik existuje různých pořadí střelců?
(b) Při tomto pořadí střelců:

lze vývoj skóre zaznamenat jako . Každý vývoj skóre (každé pořadí log týmů) se objeví při několika pořadích střelců. Při kolika?

Výsledek: (skrýt)

(a): $7! = 5040$ , (b): $3!\cdot 4! = 144$ , (c): $7!/(3!\cdot 4!) = 35$ .

Výsledek

Řešení: (skrýt)

Střelců je 7, a tak je jejich možných pořadí $7! = 5040$ .
Při pevném vývoji skóre je k přiřazení střelců třeba určit, v jakém pořadí se trefovali floridští střelci a v jakém ti z Tampa Bay. Čtyři floridští se trefili v jednom ze $4!$ pořadí a tři z Tampy v jednom ze $3!$ pořadí. Jelikož lze každé pořadí floriských střelců zkombinovat z každým pořadím střelců z Tampy, odpověď je $4! \cdot 3! = 144$ .
V části (b) jsme zjistili, že výsledek části (a) (5040) zahrnuje každý vývoj utkání přesně $144$ krát. Možných vývojů je tak $5040/144 = 35$ .

Řešení

Úloha č. 2

(Nejde o výsledky, rozdělte podúlohy do skupin. Více.)

Následující úloha se skládá z několika podúloh. Rozdělte podúlohy do několika skupin (může to být i jen jediná skupina) tak, že všechny podúlohy v jedné skupině mají stejný výsledek. Výsledek podúloh v rámci skupiny není nutné určit a není podstatný. Hledejte důvody pro svá rozhodnutí. Skrýt.

(a) Kolika způsoby se mohlo vyvíjet skóre zápasu Tampy proti Floridě, který skončil 3:4 pro Floridu?
Která z ostatních úloh vás vede k výpočtu $\frac{7\cdot6\cdot5\cdot4\cdot3\cdot2\cdot1}{(4\cdot3\cdot2\cdot1)\cdot(3\cdot2\cdot1)}?$
(c) Následující program pracuje se seznamem střelců ze zápasu Tampy proti Floridě. Kolika možnými výpisy může program skončit? Možné výpisy jsou například (2,6,7), (1,3,5).

(d) Která z ostatních úloh vás vede k výpočtu $\frac{7\cdot6\cdot5}{3\cdot2\cdot1}?$

(e) Městský dopravní podnik se rozhodl výrazně urychlit linku ze zastávky

$A$ do

$B$ . Nová linka pojede stále z

$A$ do

$B$ , ale na trase budou zrušeny

$4$ stanice. Kolika způsoby to lze provést?

Výsledek: (skrýt)

(a) = (b) = (c) = (d) = (e)

Výsledek

Řešení: (skrýt)

(a) $\Leftrightarrow$ (b) V předchozí úloze jsme spočítali možné vývoje podle (b).
Postupně vybíráme. Na pořadové číslo gólu T.J. máme 7 možností, na p.č. gólu A.S 6 možností a na p.č. gólu S.S. máme 5 možností. Tímto jsme každou trojici započítali ve všech šesti ( $=3\cdot 2 \cdot 1$ ) pořadí a přitom ji chceme započítat jen v tom od nejmenšího k největšímu. Výsledek je pak vskutku $7\cdot 6 \cdot 5 /(3\cdot 2 \cdot 1)$ .
(a) $\Leftrightarrow$ (c) Vývoj utkání je jednoznačně určen tím, kterou trojici pořadových čísel zabírají góly Tampy. To přesně se ale počítá v (c).
(c) $\Leftrightarrow$ (e) Ke zrušení připadá v úvahu sedm zastávek. Očíslujeme je pořadovými čísly a pak je ztotožníme s góly v části (c). Vybírat trojici zastávek ke zrušení je stejné jako vybírat trojici gólů Tampy.

Řešení

Úloha č. 3

(Nejde o výsledky, rozdělte podúlohy do skupin. Více.)

Která z ostatních úloh vás vede k výpočtu $\frac{9!}{4!\cdot 5!}?$
(b) Žaneta měla devět krychlí očíslovaných čísly 1 až 9 v nějakém pořadí seřazených za sebe do řady. Pak krychle s čísly 1 až 5 přebarvila nabílo a tyto bílé krychle vrátila na jejich původní místa v řadě. Úplně stejně přebarvila načerno krychle s čísly 6 až 9 a též je vrátila. Kolik různých pořadí černých a bílých krychlí mohla získat?
(c) Kolik je pětiprvkových podmnožin devítiprvkové množiny?
Která z ostatních úloh vás vede k výpočtu čísla ${9 \choose 5}?$
Čtyři kluci a pět holek se navzájem dobře znají. Pět z těchto známých se sešlo na párty u jednoho z kluků (hostitel a $4$ hosté). Kolika způsoby lze pětici účastníků párty vybrat?

Výsledek: (skrýt)

(a) = (b) = (c) = (d)

Výsledek

Řešení: (skrýt)

Celkový počet pořadí je $9!$ . Pokud se ale podíváme na jedno konkrétní pořadí černých a bílých krychliček, započítali jsme jej jistě vícekrát. Kolika způsoby můžeme rozšířit černobílé pořadí na původní spočítáme snadno. Stačí pěti bílým krychličkám rozdat v nějakém pořadí čísla (1-5) a pak nezávisle černým krychličkám rozdat čísla 6 až 9. Na to je $5! \cdot 4!$ způsobů. Odpověď na původní otázku je pak $9!/(4!\cdot 5!)$ .
(b) $\Leftrightarrow$ (c) Výsledkem Žanetina pokusu je devítice krychlí, z nichž pět je bílých a čtyři černé. Pořadová čísla bílých krychliček tedy jednoznačně odpovídají čtyřprvkovým podmnožinám devítiprvkové množiny všech pořadových čísel.
Na minulé hodině jsme se dohodli, že symbol $\binom{9}{5}$ značí počet způsobů, jak z devítice vybrat čtveřici, přičemž na pořadí v rámci čtveřice nezáleží. Zde vybereme tu pětici prvků, která se objeví v hledané pětiprvkové podmnožině.
Tato úloha je odlišná. Z devíti známých sice vybíráme pětici, ovšem jeden takový výběr nevyhovuje podmínkám úlohy. Totiž ten, v němž vybereme pět dívek (nelze vybrat hostitele). Výsledek je pak $\binom{9}{5} - 1$ .

Řešení

Úloha č. 4

(Nejde o výsledky, rozdělte podúlohy do skupin. Více.)

Kolika různými cestami se dá dostat z nejsevernějšího města do města $A$ ?

(b) Kolik nápisů délky šest lze sestavit ze dvou znaků

$\searrow$ a čtyř znaků

$\swarrow$ ? (Např.

$\swarrow\ \swarrow\ \swarrow\ \swarrow\ \searrow\ \searrow$ nebo

$\swarrow\ \swarrow\ \searrow\ \swarrow\ \swarrow\ \searrow$ .)

$C$ ?

(d) Kolika různými cestami se dá dostat z nejsevernějšího města do města

$B$ ?

(e) Která z ostatních úloh vás vede k výpočtu ${6 \choose 2}?$

Výsledek: (skrýt)

(a) = (b) = (c) = (e)

Výsledek

Řešení: (skrýt)

Při cestování z nejsevernějšího města do města $A$ si zapisujeme, zda jsme šli směrem $\searrow$ nebo směrem $\swarrow$ . Tím vznikne nápis délky šest obsahující přesně dva znaky $\searrow$ a čtyři znaky $\swarrow$ . Pomocí popsaného procesu si jednoznačně odpovídají cesty a nápisy.
Každé cestě do $A$ jednoznačně přiřadíme osově symetrickou cestu do $C$ (a naopak) podle obrázku.

Též bychom mohli říci, že v nápisu vyměníme šipky $\searrow$ za šipky $\swarrow$ a naopak. Tedy například nápisu $\swarrow\ \swarrow\ \searrow\ \swarrow\ \swarrow\ \searrow$ odpovídá nápis $\searrow\ \searrow\ \swarrow\ \searrow\ \searrow\ \swarrow$ .

(b)

$\Leftrightarrow$ (e) V nápisu je celkem

$6$ symbolů. Vybereme dvě pozice, na nichž budou symboly

$\searrow$ , na zbývajících pozicích budou symboly

$\swarrow$ .

(d) Tato úloha je odlišná. Cesty do

$B$ se sice též dají zapsat pomocí šesti symbolů, avšak tři z nich jsou

$\searrow$ a tři

$\swarrow$ .

Řešení

Úloha č. 5

(Nejde o výsledky, rozdělte podúlohy do skupin. Více.)

Která z ostatních úloh vás vede k výpočtu ${n \choose k}?$
Kolika způsoby lze ze skupiny $n$ lidí vybrat $k$ -člennou reprezentaci?
Kolika způsoby lze ze skupiny $n$ lidí vybrat $n-k$ lidí, kteří se nedostanou do reprezentace?
Která z ostatních úloh vás vede k výpočtu ${n \choose n-k}?$

Výsledek: (skrýt)

(a) = (b) = (c) = (d)

Výsledek

Řešení: (skrýt)

Výraz $\binom{n}{k}$ značí přesně počet způsobů, kterak z $n$ lidí vybrat $k$ reprezentantů.
Vybírat $k$ -tici vybraných je totéž jako vybírat $(n-k)$ -tici nevybraných.
Ze stejného důvodu jako (a) $\Leftrightarrow$ (b).

Řešení

Úloha č. 6

Ve skupinách C a D se hrály kvalifikační zápasy. První tři týmy z každé skupiny postupily do finálové skupiny. Kvalifikační skupiny dopadly jako na obrázku.

Ve finálové skupině je možné dosáhnout libovolného pořadí týmů. V kolika z nich skončí

(a) Česká republika před Finskem? (ne nutně bezprostředně)
(b) Česká republika před Finskem i Dánskem? (Mohly se mezi ně vklínit i další týmy.)
(c) postupující týmy ze skupiny D ve vzájemně stejném pořadí? (Tj. ČR před Finskem a Finsko před Dánskem, ale ne nutně bezprostředně.)
(d) postupující týmy z obou skupin ve vzájemně stejném pořadí?

Výsledek: (skrýt)

(a) $6!/2 = \binom{6}{2} \cdot 4!= 360$ , (b) $6!/3 = \binom{6}{3} \cdot 2 \cdot 3! = 240$ , (c) $6!/3! = \binom{6}{3} \cdot 3! = 120$ . (d) $6!/(3! \cdot 3!) = \binom{6}{3} = 20$ .

Výsledek

Řešení: (skrýt)

Celkových pořadí je $6!$ a těch, v nichž je ČR před Finskem je stejně jako těch, kde je to naopak. Tedy přesně půlka.
Alternativně lze nejprve vybrat dvojici pozic pro ČR a Finsku, jedním ze $\binom{6}{2}$ způsobů, na tuto dvojici pozic jednoznačně umístit ČR a Finsko (ČR první) a zbylé čtyři týmy na zbylé čtyři pozice umístit jedním ze $4!$ způsobů. Výsledek je pak také $\binom{6}{2} \cdot 4! = 360$ .
V rámci trojice ČR, Finsko, Dánsko bude ČR na prvním místě přesně ve třetině případů, tedy v $6! / 3 = 240$ .
Alternativně podobně jako v (a) lze dospět k $\binom{6}{3} \cdot 2 \cdot 3!$ s tím, že na vybranou trojici pozci lze tentokrát trojici zemí umístit dvěma způsoby.
Každé ze šesti pořadí trojice týmů nastává mezi všemi $6!$ pořadími stejně často, a odpověď tak je $6! / 6 = 120$ .
Nebo, opět podobně jako v (a) a (b) získáme $\binom{6}{3} \cdot 3! = 120$ .
Tentokrát je jednodušší postupovat tak, že vybereme trojici pozic pro účastníky skupiny D (jedním z $\binom{6}{3}$ způsobů) a pak již jednoznačně umístím jak týmy ze skupiny D, tak i týmy ze skupiny C. Odpověď je tedy $\binom{6}{3} = 20$ .
I zde lze použít úvahu o symetrii. Každá z $3! \cdot 3!$ kombinací vzájemných pořadí týmů ze skupiny C a týmů ze skupiny D nastává stejně často. Takto dostaneme odpověď $6!/(3! \cdot 3!) = 20$ .

Řešení

Úloha č. 7

Šestnáct hráčů hraje turnaj vyřazovacím systémem (tzv. pavouk). Je známo, kdo je 1. favoritem, 2. favoritem, 3. favoritem, atd. až 16. favoritem. Počítač hráče zcela náhodně rozmístí do pavouka.

(a) Předpokládejme, že všechny zápasy vyhraje favorit. Kolikátý favorit by se ještě mohl dostat do finále?
(b) Kolikátý favorit by se ještě mohl dostat do finále, pokud by každý hráč mohl jednou překvapit (tj. porazit více favorizovaného hráče)?

Výsledek: (skrýt)

(a): 9, (b) 14

Výsledek

Řešení: (skrýt)

(a): Druhý finalista musí být vítězem své poloviny pavouka. Musí tedy být nejlepší v nějaké osmici hráčů, neboli nejhuře osmý od konce. Devátý hráč, který je osmý od konce, se skutěčně do finále dostat může, pokud jsou v jeho polovině pavouky pouze ti hůře nasazení.
(b): Čtrnáctý hráč se může dostat do finále například takto (červeně-čárkovaně jsou překvapení).

Nikdo horší se do finále dostat nemůže, neb na to jsou potřeba tři výhry, jichž 15. ani 16. hráč nemohou dosáhnout, ani když jednou překvapí.

Řešení

Shrnutí: Pro počet způsobů, kterými lze vybrat z $n$ objektů skupinu $k$ objektů, platí ${n \choose k} = \frac{n\cdot (n-1)\cdot \ldots \cdot (n-k+1)}{k\cdot(k-1)\cdot\ldots\cdot1}.$ V čitateli je součin $k$ čísel, která se postupně o jedna snižují.

Pokud v předchozím výrazu vynásobíme čitatel i jmenovatel číslem $(n-k)\cdot(n-k-1)\cdot\ldots2\cdot1$ (tedy číslem $(n-k)!$ ) nebo pokud provedeme úvahu z úlohy o obarvování kuliček, dojdeme k vyjádření ${n\choose k}=\frac{n!}{k!(n-k)!}.$

V úloze o vybírání $k$ reprezentantů a $n-k$ nereprezentantů jsme viděli, že platí ${n \choose k} = {n \choose n-k}.$

Hodiny

Bonusy

Kombinace II

Úloha č. 1

Úloha č. 2

Úloha č. 3

Úloha č. 4

Úloha č. 5

Úloha č. 6

Úloha č. 7